package com.LeeCode;

import java.util.*;

/**
 * 找到离给定两个节点最近的节点
 */

public class Code2359 {
    public static void main(String[] args) {
        int[] edges = {5,3,1,0,2,4,5};
        int node1 = 3, node2 = 2;
        System.out.println(new Code2359().closestMeetingNode(edges, node1, node2));

    }

    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;

        // 记录 node1 到各点的距离
        int[] dist1 = new int[n];
        Arrays.fill(dist1, -1);
        int d = 0;
        int cur = node1;
        while (cur != -1 && dist1[cur] == -1) {
            dist1[cur] = d++;
            cur = edges[cur];
        }

        // 记录 node2 到各点的距离
        int[] dist2 = new int[n];
        Arrays.fill(dist2, -1);
        d = 0;
        cur = node2;
        while (cur != -1 && dist2[cur] == -1) {
            dist2[cur] = d++;
            cur = edges[cur];
        }

        // 找出共同可达、且 max(d1, d2) 最小的节点
        int minDist = Integer.MAX_VALUE;
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (dist1[i] != -1 && dist2[i] != -1) {
                int maxD = Math.max(dist1[i], dist2[i]);
                if (maxD < minDist) {
                    minDist = maxD;
                    ans = i;
                } else if (maxD == minDist && i < ans) {
                    ans = i; // 编号更小的节点优先
                }
            }
        }

        return ans;
    }
}
